package org.example.dp.unidimensional;

/**
 * @Description: 组合总和  超时
 * @Author wyatt
 * @Data 2024/04/22 17:44
 */

//给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
//
// 题目数据保证答案符合 32 位整数范围。
//
//
//
// 示例 1：
//
//
//输入：nums = [1,2,3], target = 4
//输出：7
//解释：
//所有可能的组合为：
//(1, 1, 1, 1)
//(1, 1, 2)
//(1, 2, 1)
//(1, 3)
//(2, 1, 1)
//(2, 2)
//(3, 1)
//请注意，顺序不同的序列被视作不同的组合。
//
//
// 示例 2：
//
//
//输入：nums = [9], target = 3
//输出：0
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 200
// 1 <= nums[i] <= 1000
// nums 中的所有元素 互不相同
// 1 <= target <= 1000
//
//
//
//
// 进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？
//
// Related Topics 数组 动态规划 👍 1007 👎 0

public class Solution377 {

    public static void main(String[] args) {
        Solution377 solution = new Solution377();
        int[] nums = {1,2,3};
        System.out.println(solution.combinationSum42(nums, 5));
    }
    public int combinationSum42(int[] nums, int target) {

        //step1 filter > target
        int[] filterNums = new int[nums.length];
        int index = 0;
        for(int num : nums){
            if(num <= target){
                filterNums[index] = num;
                index++;
            } else {
                filterNums[index] = 0;
            }
        }

        if(index == 0){
            return 0;
        }

        //step2 从1计算到target
        int[] dp = new int[target+1];
        for(int i=1;i<=target;i++){
            for(int j=0;j<filterNums.length;j++){
                if(filterNums[j] == 0){
                    continue;
                }
                if(filterNums[j] < i){
                    dp[i] += dp[i-filterNums[j]];
                }else if(filterNums[j] == i){
                    dp[i]++;
                }
            }
        }
        return dp[target];

    }
    public int combinationSum4(int[] nums, int target) {
        //step1 filter > target
        int[] filterNums = new int[nums.length];
        int index = 0;
        int count = 0;
        for(int num : nums){
            if(num <= target){
                filterNums[index] = num;
                index++;
            } else {
                filterNums[index] = 0;
            }
        }

        if(index == 0){
            return 0;
        }

        for(int filterNum : filterNums){

            if(filterNum == 0){
                continue;
            }

            if(target - filterNum == 0){
                count++;
            } else if (target - filterNum > 0){
                count += combinationSum4(filterNums, target - filterNum);
            }
        }

        return count;
    }
}



//给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
//
// 题目数据保证答案符合 32 位整数范围。
//
//
//
// 示例 1：
//
//
//输入：nums = [1,2,3], target = 4
//输出：7
//解释：
//所有可能的组合为：
//(1, 1, 1, 1)
//(1, 1, 2)
//(1, 2, 1)
//(1, 3)
//(2, 1, 1)
//(2, 2)
//(3, 1)
//请注意，顺序不同的序列被视作不同的组合。
//
//
// 示例 2：
//
//
//输入：nums = [9], target = 3
//输出：0
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 200
// 1 <= nums[i] <= 1000
// nums 中的所有元素 互不相同
// 1 <= target <= 1000
//
//
//
//
// 进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？
//
// Related Topics 数组 动态规划 👍 984 👎 0

